import java.util.HashMap;
import java.util.Map;

/**
 * 437. 路径总和 III
 */
public class Solution_437 {
    // 前缀和，一个节点的前缀和就是该节点到根节点之间的路径和
    // key 是前缀和， value 是该前缀和的节点数量
    Map<Integer, Integer> prefix;
    int target;

    public int pathSum(TreeNode root, int targetSum) {
        prefix = new HashMap<Integer, Integer>();
        target = targetSum;

        // 前缀和为 0 的一条路径
        prefix.put(0, 1);
        return recursion(root, 0);
    }

    public int recursion(TreeNode node, int curSum) {
        if (node == null) {
            return 0;
        }

        int res = 0;
        // 当前路径上的和
        curSum += node.val;

        // 看看root到当前节点这条路上是否存在 节点前缀和+target=currSum 的路径
        // 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了
        // currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target
        res += prefix.getOrDefault(curSum - target, 0);
        // 更新路径上当前节点前缀和的个数
        prefix.put(curSum, prefix.getOrDefault(curSum, 0) + 1);

        // 进入下一层
        int left = recursion(node.left, curSum);
        int right = recursion(node.right, curSum);
        res = res + left + right;

        // 回到本层，恢复状态，去除当前节点的前缀和数量
        prefix.put(curSum, prefix.get(curSum) - 1);
        return res;
    }
}
